1. Field of the Invention
The present invention relates to scheduling independent tasks in a multi-tasking operating system embedded in a specific purpose device, and in particular to externally constraining the use of computing resources by a task that is not known to cooperatively share computing resources.
2. Description of the Related Art
A still increasing number of products in commerce include information processors. For example, greeting cards, cell phones, cameras, household appliances, automobiles, machining tools, construction tools, and network devices, such as routers, among others, are specific purpose devices that include information processors. The processor, supporting components, and processor instruction sets that support the primary purpose of such a specific purpose device constitute an embedded system.
The information processors in embedded systems are often streamlined to perform a limited set of operations related to the purpose of the product device and are not configured to perform general-purpose computing. The streamlining is evident in both hardware and processor instructions (software). For example, the hardware might include less memory and storage, fewer accelerator circuits, fewer peripherals, such as printers and other displays, and smaller power supplies than are found in a general purpose computer. Similarly, the software might include a simpler operating system with fewer drivers for peripheral devices, and a reduced number of expected states and therefore a reduced number of state variables and a reduced number of instructions to handle the various states.
It is often the case that the information processor in the embedded system is not fully utilized in performing all the functions for which the specific purpose device is designed. For example, many routers that direct data packets over communication links connecting multiple network nodes include one or more processors that are used to compute the best route for a data packet, encapsulate the data in a data packet directed to the correct link, and perform error-checking to determine that communications are successful. However, only a portion of the processor capacity is consumed in performing the primary router purpose. For example, some routers use only about 20% of the information processing capacity of their processors, which often means that one or more processors in the router are idle about 80% of the time.
It is sometimes advantageous to make use of the excess capacity of processors in embedded systems. For example, the excess capacity of a processor on a refrigerator control circuit might be used by a separate software application to compute and display the expected freshness life of different foodstuffs based on the current temperature and humidity conditions in the refrigerator and freezer sections of the appliance. Similarly, the excess capacity of a processor on a network router might be used by a separate software application to provide services over and beyond those usually associated with a router, such as providing information to users on geo-spatial relationships among the network elements and hosts in a network. As another example, an end node connected to a network might have more data to process in a particular interval of time than it can handle; and so the end node sends a part of the data and the instructions to process that data to each of one or more of the closest routers on the network, using the router computing capacity to complete the processing in the available time interval.
There are problems associated with tapping the unused capacity of processors in embedded systems, however. For example, the extra application (called here a “foreign application”) that is not related to the specific purpose of the device, may consume more than the excess capacity of the processor in the specific purpose device, and, thus, interfere with the proper functioning of the device for its specific purpose. For example, a router might no longer be able to route all the data packet traffic the router receives because the foreign application has consumed more than 80% of the capacity of the router's processor in order to perform the computations on the data sent from the end node.
Embedded systems typically include multi-tasking schedulers which divide time on a processor among multiple sequences of processor instructions called tasks. Each task typically uses the processor to do one specific job, such as reading a sensor, scanning a keyboard or mouse, logging some type of data, performing a calculation on numbers in one or more registers, and sending data over a bus to a device or communication link. It is desirable that the scheduler for an embedded system ensure that the primary purpose of the device is accomplished even if some computing capacity is provided to foreign applications.
Typically, embedded system task schedulers assigns each task a priority that determines when it is given access to the processor relative to other tasks. Higher priority tasks are performed before lower priority tasks. When multiple tasks have the same high priority, a policy is used to determine which task is allowed to execute on the processor next. A common policy, called a “round robin” policy, is to take each task of the same priority in turn. Each task is allowed to run to completion and then the next task at the highest priority is allowed to use the processor.
For such a collection of tasks to successfully share a processor, the tasks must be designed to be cooperative, i.e., to prevent one task from “starving” by being unable to use the processor within a useful period of time. It is common for all the tasks associated with an embedded system to be designed to cooperate in the use of a processor. Each cooperative task uses the processor for a limited time and then yields the processor for use by other tasks.
However, instructions for foreign applications are not necessarily designed to be cooperative, and a scheduler for an embedded system can not rely on instructions internal to each task to provide the necessary sharing. One reason instructions from a foreign application might not be cooperative is that they were designed for operation on a general purpose computer in which a language compiler or a full operating system externally enforces a policy of sharing use of a processor. Thus, if such an uncooperative task is given control of the processor in an embedded system, the task might not yield the processor in time for subsequent equal or higher-priority tasks to use the processor. Thus the priority based schedulers typical in embedded systems are not adequate for scheduling tasks from many foreign applications.
In some general purpose computing systems, strict time-slicing is enforced, so that each task is allotted only a certain time on the processor and then is moved off. Tasks moved off the processor are moved to a location in memory that preserves the state of all registers used by the task, and the stack of instructions that still need to be completed. However, in embedded systems, all tasks are not equal; tasks that support the purpose of the device and are time critical, such as realtime processes, must be allowed to complete before other tasks are started which are peripheral to the purpose of the device or are not time-critical. Strict time slicing is not compatible with guaranteeing that certain tasks, such as the time-critical tasks that support the purpose of the device, run to completion.
Thus neither a priority-based policy nor a strict time-slicing policy is adequate for a task scheduler for an embedded system that allows foreign applications.
In some approaches, various hybrids between priority and time-slicing have been employed. For example, in one approach all high-priority, ready-to-execute tasks are run before any lower priority task. Multiple ready tasks at the same priority share the processor time equally by time slicing. While suitable for some purposes, this approach still suffers some disadvantages. For example, there is no provision for guaranteeing processor time for time-critical tasks; all tasks at the same priority level have equal access to the processor, even though some tasks are time critical and others are not.
In some approaches multiple ready tasks at the same priority share the processor time by running each to completion in turn. This approach also suffers some disadvantages. Again, there is no provision for guaranteeing processor time for time-critical tasks; all tasks at the same priority level have equal chance of being run to completion next, even though some tasks are time-critical and others are not.
Based on the foregoing, there is a clear need for techniques to allocate processor time to tasks that give foreign applications adequate resources without hindering the primary purpose of an embedded system. In general, there is a need for techniques to allocate computing resources among tasks that do not suffer the disadvantages of prior art approaches. For example, there is a need for techniques to schedule tasks, which allow real-time tasks that have absolute constraints on their operation to run to completion and that also accommodate tasks that are not known to be cooperative.